package stackAndQueue.q2_twoStacksQueue;

import java.util.Stack;

/**
 * Project：algorithm
 * Date：2024/6/4
 * Time：18:26
 * Description：用两个栈实现队列，支持队列的基本操作（add、poll、peek）
 * 解法：双栈，将一个栈倒入另外一个栈，则另外一个栈可实现先进先出效果（队列）
 *     第一个栈为压入栈stackPush，压入数据都往该栈压入；第二个栈为弹出栈stackPop，弹出数据时都从该栈弹出
 *     两个要点：
 *     - 压入栈stackPush 往 弹出栈stackPop 压入数据要一次性全部压入
 *     - 弹出栈stackPop 不为空则绝对不能往stackPop中压入数据
 *     所以从 stackPush 压数据到 stackPop 的时机：执行add、poll、peek的任何一种
 *
 * @author Cao Jiwen
 * @version 1.0
 */
public class TwoStacksQueue {

    private final Stack<Integer> stackPush;
    private final Stack<Integer> stackPop;

    public TwoStacksQueue() {
        this.stackPush = new Stack<>();
        this.stackPop = new Stack<>();
    }

    /**
     * 将 压入栈 的数据 倒入 弹出栈
     */
    private void pushToPop(){
        // 弹出栈 stackPop 不为空则绝对不能压入数据
        if (stackPop.isEmpty()){
            // 一次性全部压入
            while (!stackPush.isEmpty()){
                stackPop.push(stackPush.pop());
            }
        }
    }

    public void add(int newNum){
        stackPush.push(newNum);
        pushToPop();
    }

    public int pop(){
        if (stackPop.isEmpty() && stackPush.isEmpty()){
            throw new RuntimeException("Queue is empty.");
        }
        pushToPop();
        return stackPop.pop();
    }

    public int peek(){
        if (stackPop.isEmpty() && stackPush.isEmpty()){
            throw new RuntimeException("Queue is empty.");
        }
        pushToPop();
        return stackPop.peek();
    }
}
